package cn.jietuo.first.class06;

/**
 * @author zhangx & jietuo_zx@163.com
 * @version 1.0
 * @date 2020/7/15
 * @description: 将单向链表按某值划分成左边小、中间相等、右边大的形式
 */
public class Code03_SmallerEqualBigger {

    public static class Node {
        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    public static Node listPartition1(Node head, int pivot) {
        if (head == null) {
            return head;
        }
        // 先计算出链表长度
        int i = 0;
        Node cur = head;
        while (cur != null) {
            i++;
            cur = cur.next;
        }
        Node[] arr = new Node[i];
        // 将链表放入数组中
        cur = head;
        i = 0;
        while (cur != null) {
            arr[i++] = cur;
            cur = cur.next;
        }
        partition(arr, pivot);
        for (i = 1; i < arr.length; i++) {
            arr[i - 1].next = arr[i];
        }
        arr[i - 1].next = null;
        return arr[0];
    }

    private static void partition(Node[] arr, int pivot) {
        if (arr == null || arr.length < 1) {
            return;
        }
        int small = -1;
        int big = arr.length;
        int index = 0;
        while (index < big) {
            if (arr[index].value < pivot) {
                swap(arr, ++small, index++);
            } else if (arr[index].value == pivot) {
                index++;
            } else if (arr[index].value > pivot) {
                swap(arr, index, --big);
            }
        }
    }

    private static void swap(Node[] arr, int i, int cur) {
        Node temp = arr[i];
        arr[i] = arr[cur];
        arr[cur] = temp;
    }

    public static Node listPartition2(Node head, int pivot) {
        // 小于的头尾结点
        Node sH = null;
        Node sE = null;
        // 等于的头尾结点
        Node eH = null;
        Node eE = null;
        // 大于的头尾结点
        Node mH = null;
        Node mE = null;
        Node next = null;
        while (head != null) {
            next = head.next;
            head.next = null;
            if (head.value < pivot) {
                if (sH == null) {
                    sH = head;
                    sE = head;
                } else {
                    sE.next = head;
                    sE = head;
                }
            } else if (head.value == pivot) {
                if (eH == null) {
                    eH = head;
                    eE = head;
                } else {
                    eE.next = head;
                    eE = head;
                }
            } else {
                if (mH == null) {
                    mH = head;
                    mE = head;
                } else {
                    mE.next = head;
                    mE = head;
                }
            }
            head = next;
        }

        if (sE != null) {
            sE.next = eH;
            eE = eE == null ? sE : eE;
        }
        if (eE != null) {
            eE.next = mH;
        }
        return sH != null ? sH : (eH != null ? eH : mH);
    }


    public static void printLinkedList(Node node) {
        System.out.print("Linked List: ");
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head1 = new Node(7);
        head1.next = new Node(9);
        head1.next.next = new Node(1);
        head1.next.next.next = new Node(8);
        head1.next.next.next.next = new Node(2);
        head1.next.next.next.next.next = new Node(2);
        head1.next.next.next.next.next.next = new Node(5);
        printLinkedList(head1);
        head1 = listPartition1(head1, 2);
//        head1 = listPartition2(head1, 7);
        printLinkedList(head1);

    }
}
